/**
 * @a https://leetcode.cn/problems/01-matrix/
 */

#include "../../common.h"

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        const static int dx[4] = {0,0,1,-1};
        const static int dy[4] = {1,-1,0,0};

        int row = mat.size(), col = mat[0].size();
        vector<vector<int>> dist(row, vector<int>(col, -1));

        queue<pair<int,int>> que;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(mat[i][j] == 0){
                    dist[i][j] = 0;
                    que.push({i,j});
                }
            }
        }

        while(que.size()){
            auto [a,b] = que.front();
            que.pop();
            for(int i = 0; i < 4; ++i){
                int x = a + dx[i],y = b + dy[i];
                if(x >= 0 && x < row && y >= 0 && y <col
                && dist[x][y] == -1){
                    dist[x][y] = dist[a][b] + 1;
                    que.push({x,y});
                }
            }
        }
        return dist;
    }
};